#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// https://leetcode.cn/problems/beautiful-towers-ii/
// 2866.

class Solution
{
public:
    long long maximumSumOfHeights01(vector<int> &maxHeights)
    {
        long long ans = 0;

        stack<int> recordLeftIndex;
        vector<long long> recordLeftSum(maxHeights.size(), 0);
        long long curSum = 0;
        for (int i = 0; i < maxHeights.size(); i++)
        {
            if (recordLeftIndex.empty() || maxHeights[recordLeftIndex.top()] <= maxHeights[i])
            {
                recordLeftIndex.push(i);
                curSum += maxHeights[i];
                recordLeftSum[i] = curSum;
                continue;
            }
            
            int count = 0;
            curSum += maxHeights[i];
            while (!recordLeftIndex.empty() && maxHeights[recordLeftIndex.top()] > maxHeights[i])
            {
                curSum -= maxHeights[recordLeftIndex.top()];
                curSum += maxHeights[i];
                recordLeftIndex.pop();
                count++;
            }
            for (int j = 0; j <= count; j++)
            {
                recordLeftIndex.push(i);
            }
            recordLeftSum[i] = curSum;
        }
        // 
        stack<int> recordRightIndex;
        curSum = 0;
        for (int i = maxHeights.size() - 1; i >= 0; i--)
        {
            if (recordRightIndex.empty() || maxHeights[recordRightIndex.top()] <= maxHeights[i])
            {
                recordRightIndex.push(i);
                ans = max(ans, curSum + recordLeftSum[i]);
                curSum += maxHeights[i];
                continue;
            }
            // 注释：
            // 这里的curSum是从i开始的，但是recordLeftSum[i]是从0开始的，所以要加上recordLeftSum[i]
            // 这里的curSum是从i开始的，但是recordLeftSum[i]是从0开始的，所以要加上recordLeftSum[i]
            int count = 0;

            while (!recordRightIndex.empty() && maxHeights[recordRightIndex.top()] > maxHeights[i])
            {
                curSum -= maxHeights[recordRightIndex.top()];
                curSum += maxHeights[i];
                recordRightIndex.pop();
                count++;
            }
            for (int j = 0; j <= count; j++)
            {
                recordRightIndex.push(i);
            }
            ans = max(ans, curSum + recordLeftSum[i]);
            curSum += maxHeights[i];
        }
        return ans;
    }

    // 优化
    long long maximumSumOfHeights(vector<int> &maxHeights)
    {
        long long ans = 0;

        stack<int> recordLeftIndex;
        vector<long long> recordLeftSum(maxHeights.size(), 0);
        long long curSum = 0;
        for (int i = 0; i < maxHeights.size(); i++)
        {
            if (recordLeftIndex.empty() || maxHeights[recordLeftIndex.top()] <= maxHeights[i])
            {
                recordLeftIndex.push(i);
                curSum += 1LL * maxHeights[i];
                recordLeftSum[i] = curSum;
                continue;
            }
            // 记录
            // curSum += maxHeights[i];
            while (!recordLeftIndex.empty() && maxHeights[recordLeftIndex.top()] > maxHeights[i])
            {
                int curTop = recordLeftIndex.top();
                recordLeftIndex.pop();
                if (!recordLeftIndex.empty())
                {
                    curSum -= maxHeights[curTop] * (curTop - recordLeftIndex.top());
                }
                else
                {
                    curSum -= maxHeights[curTop] * max(curTop + 1, 1);
                }
            }
            int curTop = recordLeftIndex.empty() ? -1 : recordLeftIndex.top();
            curSum += 1LL * (i - curTop) * maxHeights[i];
            recordLeftIndex.push(i);
            recordLeftSum[i] = curSum;
        }
        // 
        stack<int> recordRightIndex;
        curSum = 0;
        for (int i = maxHeights.size() - 1; i >= 0; i--)
        {
            if (recordRightIndex.empty() || maxHeights[recordRightIndex.top()] <= maxHeights[i])
            {
                recordRightIndex.push(i);
                curSum += 1LL * maxHeights[i];
                ans = max(ans, curSum + recordLeftSum[i] - maxHeights[i]);
                continue;
            }
            // 记录
            // curSum += maxHeights[i];
            while (!recordRightIndex.empty() && maxHeights[recordRightIndex.top()] > maxHeights[i])
            {
                int curTop = recordRightIndex.top();
                recordRightIndex.pop();
                if (!recordRightIndex.empty())
                {
                    curSum -= maxHeights[curTop] * (recordRightIndex.top() - curTop);
                }
                else
                {
                    curSum -= maxHeights[curTop] * max((int)(maxHeights.size() - curTop), 1);
                }
            }
            int curTop = recordRightIndex.empty() ? maxHeights.size() : recordRightIndex.top();
            curSum += 1LL * (curTop - i) * maxHeights[i];
            recordRightIndex.push(i);

            ans = max(ans, curSum + recordLeftSum[i] - maxHeights[i]);
        }
        return ans;
    }
};

int main()
{
    Solution soluiont{};
    vector<int> nums{999999999, 1000000000, 999999999};
    cout << soluiont.maximumSumOfHeights(nums) << endl;
    return 0;
}